Matrice d'adjacence

Définition

Soit  \(n\) un entier naturel non nul. On considère un graphe  \(G\) d’ordre  \(n\) dont les sommets sont
numérotés de  \(1\) à \(n\) , puis rangés dans l’ordre croissant de leurs numéros.

La matrice d’adjacence de  \(G\) est la matrice carrée  \(A\) de taille \(n \times n\) , dont le coefficient  \(a_{ij}\) est égal au nombre d’arêtes partant du sommet  \(i\) pour arriver au sommet \(j\) .

Remarque

Si le graphe  \(G\) n’est pas orienté, alors la matrice d’adjacence  \(A\) est une matrice symétrique.

Exemple 1

Ici,  \(G\) n’est pas orienté et il est d’ordre \(9\) .

Sa matrice d’adjacence est symétrique de taille \(9 \times 9\) .

\(A=\begin{pmatrix}0 & 1 & 0&0 & 0 & 0&0 & 0 & 0\\1 & 0 & 0&1 & 1 & 1&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\\0 & 1 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 1 & 0&1 & 0 & 0&1 & 1& 0\\0 & 1 &1&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&1\\0&0&0&0&0&1&0&1&0\end{pmatrix}\)

Exemple 2

Ici,  \(G\) est orienté et il est d’ordre \(9\) .

Sa matrice d’adjacence est de taille  \(9 \times 9\) mais n’est pas symétrique.

\(A= \begin{pmatrix}0 & 0 & 0&1 & 0 & 0&0 & 0 & 0\\1 & 0 & 1&1 & 0 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\\0 & 0 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 0&1 & 1& 1\\0 & 1 & 1&0 & 0 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 0&0 & 1 & 0\\0 & 0 & 0&0 & 0 & 0&0 & 0 & 1\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\end{pmatrix}\)